package doublePointer;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @Author cyz
 * @Date 2025/6/26 16:07
 * @Version 1.0
 **/

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 *
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 */
public class Question4 {

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap1(height));
    }

    /**
     * 动态规划
     * @param height
     * @return
     */
    public static int trap1(int[] height){
        int ans = 0;
        int leftMax = height[0];
        int rightMax = height[height.length - 1];

        int[] leftMaxs = new int[height.length];
        int[] rightMaxs = new int[height.length];

        for (int i = 0; i < height.length; i++){
            if (height[i] > leftMax){
                leftMax = height[i];
            }
            if (height[height.length -1 - i] > rightMax){
                rightMax = height[height.length - 1 - i];
            }
            leftMaxs[i] = leftMax;
            rightMaxs[height.length - 1 - i] = rightMax;
        }

        for (int i = 0; i < height.length; i++){
            int min = Math.min(leftMaxs[i], rightMaxs[i]);
            ans += min - height[i];
        }

        return ans;
    }

    /**
     * doublePointer
     * @param height
     * @return
     */
    public static int trap(int[] height){
        int ans = 0;

        int left = 0;
        int right = height.length - 1;

        int leftMax = height[0];
        int rightMax = height[height.length - 1];

        while (left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax){
                ans += leftMax - height[left];
                left++;
            }else {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }
}
